package primary.code09_dynamicTree;

import primary.code05_Tree.Node;
import lombok.extern.slf4j.Slf4j;

/**
 * 求解一个二叉树 两个节点之间的最大距离
 * <p>

 * 树形DP基本套路（从左右子树的信息推断出整树的信息）
 * step 1: 以某个节点N为头的子树中，分析答案有哪些可能性。并且，以N左子树，N右子树和N整棵树的角度考虑；
 * step 2: 根据可能性分析，列出所有需要的左右子树信息；
 * step 3: 合并第二步信息，对左右子树提出相同的要求；
 * <p>
 * 树形DP的核心：
 * 1. 最长距离可能包含本节点，也可能不包含本树节点；
 * 2. 不包含本节点，则需要左右子树的最大距离信息；包含本节点，则需要左右子树的最大深度信息；
 * 3. 本节点的最大距离为 MAX(左子树最大距离, 右子树最大距离, 左+右子树深度+1)
 */
@Slf4j
public class Code01_MaxDistance {

    /**
     * 获取二叉树 两个节点之间的最大距离
     */
    public static int maxDistance(Node root) {
        if (root == null) {
            return 0;
        }
        return maxDistanceAndMaxDepth(root)[0];
    }

    private static int[] maxDistanceAndMaxDepth(Node root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = maxDistanceAndMaxDepth(root.left);
        int[] right = maxDistanceAndMaxDepth(root.right);
        int distance = Math.max(Math.max(left[0], right[0]), left[1] + right[1] + 1);
        int depth = Math.max(left[1], right[1]) + 1;
        return new int[]{distance, depth};
    }


    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(3);
        root.right = new Node(8);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.left = new Node(7);
        root.right.right = new Node(9);
        root.right.right.right = new Node(10);
        //ans: 6
        log.info("max distance is {}", maxDistance(root));
    }
}
